#include <bits/stdc++.h>
#include "QuickSort.h"
using namespace std;

int main(){
    int n,x;
    clock_t begin,end;
    double time;
    cin >> n;
    vector<int> data,v1,v2;
    data.clear();
    for(int i=0; i < n; i++) {
        cin >> x;
        data.push_back(x);
    }


    v1=data;
    begin=clock();
    RandomQuickSort(v1,0,n-1);
    end=clock();
    time=(double)(end-begin)/CLOCKS_PER_SEC;
    for(int i=0;i<v1.size();i++){
        cout<<v1[i]<<' ';
    }
    cout<<endl;
    cout<<time<<endl;

    v2=data;
    begin=clock();
    Median3QuickSort(v2,0,n-1);
    end=clock();
    time=(double)(end-begin)/CLOCKS_PER_SEC;
    for(int i=0;i<v2.size();i++){
        cout<<v2[i]<<' ';
    }
    cout<<endl;
    cout<<time<<endl;

    return 0;
}